package org.skywork.top.core.algorithm.num;

import java.util.Arrays;

/**
 * 寻找两个正序数组的中位数
 */
public class no_4 {

    /**
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        /**
         * 示例 1：
         *
         * 输入：nums1 = [1,3], nums2 = [2]
         * 输出：2.00000
         * 解释：合并数组 = [1,2,3] ，中位数 2
         *
         * 示例 2：
         *
         * 输入：nums1 = [1,2], nums2 = [3,4]
         * 输出：2.50000
         * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
         */

        double mid = 0d;
        if(nums1.length == 0 && nums2.length == 0){
            return mid;
        }

        if(nums1.length == 0){
            if(nums2.length % 2 == 0){
                mid = (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2d;
            }else{
                mid = nums2[nums2.length / 2];
            }
            return mid;
        }

        if(nums2.length == 0){
            if(nums1.length % 2 == 0){
                mid = (nums1[nums1.length / 2] + nums1[nums1.length / 2 - 1]) / 2d;
            }else{
                mid = nums1[nums1.length / 2];
            }
            return mid;
        }

        int num = nums1.length + nums2.length;
        int[] num3 = new int[num];
        System.arraycopy(nums1, 0, num3, 0, nums1.length);
        System.arraycopy(nums2, 0, num3, nums1.length, nums2.length);
        Arrays.sort(num3);
        if(num % 2 == 0){
            mid = (num3[num / 2] + num3[num / 2 - 1]) / 2d;
        }else{
            mid = num3[num / 2];
        }
        return mid;
    }

}
